//
//  main.c
//  基数排序_Radix_sort
//
//  Created by Song on 2018/5/14.
//  Copyright © 2018年 Song. All rights reserved.
//

#include <stdio.h>
#define num 9 // 数组长度

// 获取数组a中最大值
int get_max(int a[],int n) { // n:数组长度
    int i, max;
    
    max = a[0];
    for (i = 1; i<n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

// 对数组按照“某个位数”进行排序（桶排序）
void count_sort(int a[], int n, int exp) { // exp：指数。对数组a按照该指数进行排序
    /*
        例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
           (1) 当exp=1表示按照"个位"对数组a进行排序
           (2) 当exp=10表示按照"十位"对数组a进行排序
           (3) 当exp=100表示按照"百位"对数组a进行排序
     */
    
    int output[n]; // 存储"被排序数据"的临时数组
    int i, buckets[num+1] = {0};
    
    // 将数据出现的次数存储在buckets[]中  (桶排序的思想)
    for (i = 0; i<n; i++) {
        buckets[ (a[i]/exp)%10 ]++;
//        printf(" = buckets[%d] = %d = \n",i,buckets[i]);
    }
    
    // 更改buckets[i]。让更改后的buckets[i]的值，是该数据在output[]中的位置
    for (i = 1; i < n+1; i++) {
        buckets[i] += buckets[i-1];
    }
    
    // 将数据存储到临时数组output[]中
    for (i = n-1; i>=0; i--) {
        output[buckets[ (a[i]/exp)%10 ] -1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }
    
    // 将排序好的数据赋值给a[]
    for (i=0; i<n; i++) {
        a[i] = output[i];
    }
}

// 基数排序
void radix_sort(int a[], int n) {
    int exp;
    int max = get_max(a, n); // 获取到数组中最大的数
    
    printf(" = max = %d = \n",max);
    
    // 从个位开始，对数组a按“指数”进行排序
    for (exp = 1; max/exp > 0; exp *= 10) {
        count_sort(a, n, exp);
    }
}

int main(int argc, const char * argv[]) {
    
    int a[] = {53, 3, 542, 748, 14, 2015, 154, 63, 616};
    
    radix_sort(a, num);
    
    for (int i=0; i<num; i++) {
        printf("%d ", a[i]);
    }
    
    printf("\n");
    
    return 0;
}
